#define _CRT_SECURE_NO_WARNINGS 1
//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
//输入：root = [1, null, 2, 3]
//
//输出：[1, 2, 3]
#include<iostream>
#include<vector>
#include<stack>
using namespace std; 

   
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
 
class Solution {
public:
    //利用栈返回，访问左路结点右子树
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;

        //左路结点
        //左路节点的右子树
        TreeNode* cur = root;
        while (cur || !s.empty())
        {
            //左路结点访问,并入栈
            while (cur)
            {
                v.push_back(cur->val);
                s.push(cur);

                cur = cur->left;
            }

            //子问题方式访问左路节点右子树
            TreeNode* top = s.top();
            s.pop();

            cur = top->right;//通过这一步访问右子树
        }
        return v;
    }
};
int main()
{}